package arrays;

/**
 * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
 * <p>
 * [
 * [1,   4,  7, 11, 15],
 * [2,   5,  8, 12, 19],
 * [3,   6,  9, 16, 22],
 * [10, 13, 14, 17, 24],
 * [18, 21, 23, 26, 30]
 * ]
 * <p>
 * 给定 target = 5，返回 true
 * <p>
 * 给定 target = 20，返回 false
 */
public class 二维数组中的查找 {
	public static void main(String[] args) {
		int[][] matrix = new int[][]{
				new int[]{1, 4, 7, 11, 15},
				new int[]{2, 5, 8, 12, 19},
				new int[]{3, 6, 9, 16, 22},
				new int[]{10, 13, 14, 17, 24},
				new int[]{18, 21, 23, 26, 30}
		};
		System.out.printf("数组的行数----%s",matrix.length);
		System.out.printf("数组的列数----%s",matrix[0].length);
		System.out.println(findNumberIn2DArray(matrix,12));
		System.out.println(findNumberIn2DArray(matrix,66));
	}

	public static boolean findNumberIn2DArray(int[][] matrix, int target) {
		if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
			return false;
		}
		//数组的行数
		int rows = matrix.length;
		//数组的列数
		int columns = matrix[0].length;
		//初始的行和列
		int rowBegin = 0, columnBegin = columns - 1;
		while (rowBegin < rows && columnBegin >= 0) {
			int number = matrix[rowBegin][columnBegin];
			if (number == target) {
				return true;
			} else if (number < target) {
				//如果小于目标值，则行数加一行，因为行的增长速度比列增长的慢
				rowBegin++;
			} else {
				//如果大于目标值，则列减一行
				columnBegin--;
			}
		}
		return false;
	}
	/**
	 * 可以看成一颗二叉搜索树，
	 *   1,   4,  7, 11, 15,
	 *   2,   5,  8, 12, 19,
	 *   3,   6,  9, 16, 22,
	 *   10, 13, 14, 17, 24,
	 *   18, 21, 23, 26, 30
	 *把整个二维数组顺时针旋转90度，可以发现类似一颗二叉搜索树，就类似于树的深度优先搜索了
	 *
	 *
	 *
	 */
}
